/**
 * 从第一行任意一个出发，可以走到下一行的三个格子
 * 问从上到下的最小代价
 * 
 */
class Solution {

using vi = vector<int>;

enum {None = 0x2F3F4F5F};

vector<vi> *pdata;
vector<vi> D;
int N;


public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        pdata = &matrix;
        N = matrix.size();
        D.assign(N, vi(N, None));
        int ans = None;
        for(int i=0;i<N;++i){
            chkmin(ans, dp(0, i));
        }
        return ans;
    }

    int dp(int r, int c){
        if(None != D[r][c]) return D[r][c];
        if(r + 1 == N) return D[r][c] = (*pdata)[r][c];

        int ans = None;
        for(int i=c-1;i<=c+1;++i){
            if(0 <= i and i < N){
                chkmin(ans, dp(r + 1, i));
            }
        }
        return D[r][c] = ans + (*pdata)[r][c];
    }

    void chkmin(int & d, int a){
        if(None == a) return;
        if(d == None or a < d) d = a;
    }
};